Array nesting

Time: O(N); Space: O(1); med

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1]. Sets S[K] for 0 <= K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], … }. Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example 1:

Input: nums = [5,4,0,3,1,6,2]

Output: 4

Explanation:

• A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

• One of the longest S[K]:

• S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Notes:

• N is an integer within the range [1, 20,000].

• The elements of A are all distinct.

• Each element of array A is an integer within the range [0, N-1].

1. Brute Force [Time Limit Exceeded]

The simplest method is to iterate over all the indices of the given nums array. For every index i chosen, we find the element nums[i] and increment the count for a new element added for the current index i. Since nums[i] has to act as the new index for finding the next element belonging to the set corresponding to the index i, the new index is j = nums[i].

We continue this process of index updation and keep on incrementing the count for new elements added to the set corresponding to the index i. Now, since all the elements in nums lie in the range (0,…, N-1), the new indices generated will never lie outside the array size limits. But, we’ll always reach a point where the current element becomes equal to the element nums[i] with which we started the nestings in the first place. Thus, after this, the new indices generated will be just the repetitions of the previously generated ones, and thus would not lead to an increase in the size of the current set. Thus, this condition of the current number being equal to the starting number acts as the terminating condition for countcount incrementation for a particular index.

We do the same process for every index chosen as the starting index. At the end, the maximum value of count obtained gives the size of the largest set.

class Solution1(object):
    """
    Time complexity : O(n^2). In worst case, for example- [1,2,3,4,5,0], loop body will be executed n^2 times.
    Space: O(1). Constant space is used.
    """
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                continue

            start, count = nums[i], 1
            while abs(start) != i:
                start = nums[abs(start)]
                count += 1
                nums[abs(start)] *= -1

            result = max(result, count)

        return result

class Solution1a(object):
    """
    Time complexity : O(n^2). In worst case, for example- [1,2,3,4,5,0], loop body will be executed n^2 times.
    Space: O(1). Constant space is used.
    """
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def search(idx):
            count = 0
            while nums[idx] >= 0:
                count += 1
                next_val = nums[idx]
                nums[idx] = -1
                idx = next_val
            return count

        result = 0
        for x in range(len(nums)):
            if nums[x] >= 0:
                result = max(result, search(x))

        return result

s = Solution1()
nums = [5,4,0,3,1,6,2]
assert s.arrayNesting(nums) == 4
s = Solution1a()
nums = [5,4,0,3,1,6,2]
assert s.arrayNesting(nums) == 4

2. Using Visited Array

Algorithm In the last approach, we observed that in the worst case, all the elements of the numsnums array are added to the sets corresponding to all the starting indices. But, all these sets correspond to the same set of elements only, leading to redundant calculations.

We consider a simple example and see how this problem can be resolved. From the figure below, we can see that the elements in the current nesting shown by arrows form a cycle. Thus, the same elements will be added to the current set irrespective of the first element chosen to be added to the set out of these marked elements.

Thus, when we add an element nums[j]nums[j] to a set corresponding to any of the indices, we mark its position as visited in a visitedvisited array. This is done so that whenever this index is chosen as the starting index in the future, we do not go for redundant countcount calculations, since we’ve already considered the elements linked with this index, which will be added to a new(duplicate) set.

By doing so, we ensure that the duplicate sets aren’t considered again and again.

Further, we can also observe that no two elements at indices ii and jj will lead to a jump to the same index kk, since it would require nums[i] = nums[j] = knums[i]=nums[j]=k, which isn’t possible since all the elements are distinct. Also, because of the same reasoning, no element outside any cycle could lead to an element inside the cycle. Because of this, the use of visitedvisited array goes correctly.

class Solution2(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        visited = [False] * len(nums)
        result = 0
        for i in range(len(nums)):
            count = 0
            while not visited[i]:
                count += 1
                visited[i] = True
                i = nums[i]
            result = max(result, count)
        return result

s = Solution2()
nums = [5,4,0,3,1,6,2]
assert s.arrayNesting(nums) == 4

3. Without Using Extra Space

Algorithm In the last approach, the visitedvisited array is used just to keep a track of the elements of the array which have already been visited. Instead of making use of a separate array to keep track of the same, we can mark the visited elements in the original array numsnums itself. Since, the range of the elements can only be between 1 to 20,000, we can put a None value at the position which has been visited. The rest process of traversals remains the same as in the last approach.

class Solution3(object):
    """
    Time: O(n). Every element of the numsnums array will be considered atmost once.
    Space: O(1). Constant Space is used.
    """
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for num in nums:
            if num != None:
                start, count = num, 0
                while nums[start] != None:
                    temp = start
                    start = nums[start]
                    nums[temp] = None
                    count += 1
                result = max(result, count)

        return result

s = Solution3()
nums = [5,4,0,3,1,6,2]
assert s.arrayNesting(nums) == 4

See also:

https://leetcode.com/problems/array-nesting